填充每个节点的下一个右侧节点指针 II

题目链接

117. 填充每个节点的下一个右侧节点指针 II

题目

给定一个二叉树：

struct Node {
   int val;
   Node *left;
   Node *right;
   Node *next;
}

填充每个节点的 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

思路

这个问题与 LeetCode 116 号题非常相似，都是填充二叉树的 next 指针。但是，与 116 号题不同的是，这里不再是完美二叉树，因此我们不能只使用同一层的节点之间的指针传递，还需要通过辅助指针来处理不同层级的节点。

我们可以采用层序遍历的方式来解决这个问题。具体地，我们使用两个指针：

1. curr 指针用于遍历当前层的节点。
2. nextLevelHead 和 prev 用于维护下一层的节点链接。

每次遍历当前层时，我们通过 curr 指针遍历每个节点，并将它们的左右子节点通过 prev 指针链接起来。完成一层的遍历后，我们移动到下一层继续遍历。

代码

/**
 * // Definition for a _Node.
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function(root) {
  if (!root) return null;

  let cur = root;

  while (cur) {
    let dummy = new Node(0);  // 虚拟节点，用于连接下一层的节点
    let tail = dummy;  // 指向当前已连接的最后一个节点

    while (cur) {
      if (cur.left) {
        tail.next = cur.left;  // 连接左子节点
        tail = tail.next;  // 更新尾部节点
      }
      if (cur.right) {
        tail.next = cur.right;  // 连接右子节点
        tail = tail.next;  // 更新尾部节点
      }
      cur = cur.next;  // 移动到当前层的下一个节点
    }

    cur = dummy.next;  // 移动到下一层的第一个节点
  }

  return root;
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。我们需要遍历每个节点一次。
• 空间复杂度：$O(1)$，不考虑递归栈空间，使用常数空间。